We give a new characterization of $\mathsf{NL}$ as the class of languageswhose members have certificates that can be verified with small error inpolynomial time by finite state machines that use a constant number of randombits, as opposed to its conventional description in terms of deterministiclogarithmic-space verifiers. It turns out that allowing two-way interactionwith the prover does not change the class of verifiable languages, and that nopolynomially bounded amount of randomness is useful for constant-memorycomputers when used as language recognizers, or public-coin verifiers. Acorollary of our main result is that the class of outcome problemscorresponding to O(log n)-space bounded games of incomplete information wherethe universal player is allowed a constant number of moves equals NL.
展开▼
